package likou


func GetChaoticSequence(n int) [][]int{
	var dfs func([]int)
	var rst = make([][]int, 0)
	var used = make([]bool, n)

	dfs = func(path []int) {
		// 突破100长，也不要了
		if len(rst) > 100 {
			return
		}
		// 终止条件
		if len(path) == n {  // 全排列
			temp := make([]int, n)
			copy(temp, path)
			rst = append(rst, temp)
			return
		}

		for i := 0; i < n; i++ {
			// 剪枝1. i + 1值是否能用。 元素不可重复使用
			if used[i] {
				continue
			}
			// 剪枝2.  第 i 个位置 不能放 i(下表从1开始)
			if len(path) + 1 == i + 1{
				continue
			}
			// 标记当前值 i + 1 已用： i 从0开始, 若 n = 3, i + 1 才对应 1, 2, 3
			used[i] = true
			path = append(path, i + 1)
			dfs(path)
			// 回溯去掉修改
			used[i] = false
			path = path[: len(path) - 1]
		}
	}

	dfs(make([]int, 0))
	return rst
}

